This invention relates generally to computer-based three dimensional modeling systems and specifically to a modeling system that allows the animation of a character based on the placement of footsteps.
Computer graphics technology has progressed to the point where computer-generated images rival video and film images in detail and realism. Using computer graphics techniques, a user is able to model and render objects in order to create a detailed scene. However, the tools for animating the object are inefficient and burdensome to a user, especially when it comes to animating models of living beings such as animals or humans. Many motions such as walking, running, hopping, jumping, etc., commonly made by a bipedal character are extremely difficult to describe and input into a computer system for purposes of making the three-dimensional model of the character move in a smooth and lifelike way.
One technique to realistically animate a computer model of a human character is to use data capture with live actors. Points on a human actor's body are monitored and are translated into points in a computer three-dimensional coordinate system. While the actor's movements are translated into realistic movements in a computer animation, this technique is costly, is limited to the physical performance of the actor and has restrictions on the types of movements that can be captured.
Other techniques are more closely related to standard computer aided design and computer modeling approaches. One such approach is to use keyframes that each specify an orientation of the character in one frame of an animation sequence. A first keyframe could show the character standing still while a second keyframe shows the character's right leg partially raised and moved forward from the body. The two keyframes are spaced apart by a selected amount and the computer system interpolates the "in-between" frames to provide smooth animation.
While keyframes reduce a user's or animator's work in animating a living character, such as a human, the user is required to deal with mathematical and spatial concepts of motion mechanics, animation timing, etc. The problem is that the user must place major body parts such as the knee, foot, or torso in accurate locations with respect to each other and with respect to their locations in a previous keyframe. This means that the user needs to have a knowledge of body kinematics and must be able to envision the moving character in time and space and translate the character's movements into a series of positions at specific instances in time. The problem is compounded by the fact that keyframe animation techniques typically employ interpolation functions that merely provide for the continuity of position and speed of the body parts (spline interpolation) without taking into account the mechanics of movement of the entire body. The result of such a simple keyframe approach is that the character's movements are often not life-like or natural in the animation.
Keyframe computer animation was pioneered at the University of Utah by Ivan Sutherland and his students in the early 1970's. Many extensions to keyframe animation techniques have been published that focus on the design and properties of piecewise continuous interpolating splines. See, for example, Kochanek D., et al., "Interpolating Splines with Local Tension, Continuity, and Bias Control," SIGGRAPH proceedings, 1984; and Steketee S., et al., "Parametric Keyframe Interpolation Incorporating Kinetic Adjustment and Phrasing Control," SIGGRAPH Proceedings, 1985.
Until only recently the computer animation of articulated figures, such as legged animals and human forms, was carried out using general-purpose key-frame computer animation systems. These systems could be used to animate articulated limbs by interpolating joint angles. Computing the limb's cartesian-space position from its joint angles is called "forward kinematics."
However, a major shortcoming of these systems is that joint interpolation may not be used to move the end of the limb along a specific path. Goal-directed movements, such as moving the hand to open a door, or planting a foot at a specific place on the ground, require the computation of inverse-kinematics--solving for the set of joint angles which place the end of the limb at a desired location and orientation. See Whitney, D. E., "Resolved Motion Rate Control of Manipulators and Human Prostheses," IEEE Transactions on Man-Machine Systems, MMS-10(2) pp. 47-53, June, 1969. Research in the robotics community on inverse-kinematic control has been successfully applied to computer animation. See Korein, J. U., et al., "Techniques for Generating the Goal-Directed Motion of Articulated Structures," IEEE Computer Graphics and Applications, November 1982, pp. 71-81; Girard, M., et al., "Computational Modeling for the Computer Animation of Legged Figures," ACM Computer Graphics, SIGGRAPH Proceedings, 1985; and Girard, M., "Interactive Design of 3D Computer-Animated Legged Animal Motion," IEEE Computer Graphics and Applications, June 1987.
Attempts have been made to employ higher-level movement notations borrowed from dance, such as Labanotation, see T. W. Calvert, et al., "Aspects of the Kinematic Simulation of Human Movement," IEEE Computer Graphics and Applications, November 1982. These systems "compile" labanotation into a sequence of body postures that are designated in terms of joint angles. The body postures are interpolated, using forward kinematics, into a human motion. However, with systems using this approach it is impossible to automate the motion of a figure in a simple manner, such as by specifying a path through space.
A recent trend in articulated animation research has been directed toward incorporating the simulation of "dynamics" computing the relation between joint forces and joint accelerations. As with kinematic problems, robotics research on the dynamics of articulated limbs has led to efficient general purpose methods. See Featherstone, Robot Dynamics Algorithms (Kluwer Academic Publishers, Boston, Mass. 1988). Some of these methods have been employed in computer animation systems. See Armstrong, W. W., et al., "Near-Real-Time Control of Human Figure Models," Graphics Interface, 1986; and Wilhelms, J. P., "Graphical Simulation of the Motion of Articulated Bodies Such as Humans and Robots, with Particular Emphasis on the Use of Dynamic Analysis," PhD. Dissertation, University of California, Berkeley, 1985.
However, the mechanics of movement may not be derived solely from dynamic simulation unless the articulated animal is a passive string of linked bodies, such as a marionette. The forces necessary for coordinated animal movements, such as reaching and walking, must somehow be determined. Due to the nonlinear relationship between joint forces and limb movement, and the need to satisfy constraints on a movement's path, speed, and energy expenditure, modeling coordinated motion is fundamentally a problem of control. See, Raibert, M., et al., "Animation of Dynamic Legged Locomotion," ACM Computer Graphics, SIGGRAPH Proceedings, 1991.
To date, the most advanced computer animation products for animating articulated animals employ forward and inverse kinematics as a means of animating individual limbs but lack any higher-level modeling of motions of the animal as a whole. The "Actor" module of the "Creative Environment" from SoftImage, Inc. and the "Kinemation" module from Wavefront Technologies, Inc. represent the state-of-the-art of currently available commercial systems.
In these systems, the animator must control the character as a collection of connected kinematic chains. Constraints that plant the feet and hold them in place using inverse kinematics may be dynamically orchestrated to, for example, make a human-like character run forward. But the dynamics of the motion of the body under the influence of gravity and its balance over the center-of-mass must be achieved "by hand," with no support from the program.
Similarly, a system that is targeted at choreographers, called "LifeForms," from Kinetic Effects, Inc., provides only standard forward and inverse-kinematic techniques, with the exception of a special purpose walking module that provides some high-level control over walking in a straight line. See Bruderlin, A., et al., "Goal-Directed Dynamic Animation of Human Walking," ACM Computer Graphics Vol. 23, No. 3, July 1989. While these products provide some assistance to a user in animating a character they fail to free the user from much of the burden of determining body positions in order to create natural looking animations. Also, the user interfaces for these products do not provide simple and efficient ways to create lengthy and complex animations of lifelike characters.